Many three dimensional (3D) detection and segmentation problems are confronted with searching in a high dimensional space. For example, a 3D similarity transformation is characterized by nine parameters: three position parameters, three orientation parameters and three scale parameters. It is very expensive to search the entire space for detection of an object. The search for all these parameters becomes computationally prohibitive, even if coarse-to-fine strategies are involved. Moreover, training a discriminative classifier using positive and negative examples for an object with so many parameters is challenging, because hardware limitations only allow a relatively small number of negatives at a time (on the order of 106). To handle all the possible negative examples, multiple levels of bootstrapping have to be employed, making the whole system even slower.
But there are many cases when the objects to be detected are naturally aligned in some way. For example, most faces in pictures are approximately horizontal and have approximately the same skin color. Similarly, most hearts in CT scans have approximately the same size and orientation. There is a need for a method for fast detection of an object in a high dimensional space in which the search space can be greatly reduced while still retaining accurate results.